백준 1202번: 보석 도둑

문제

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)

다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)

다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)

모든 숫자는 양의 정수이다.

출력

첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.

예제 입력 1

2 1
5 10
100 100
11

예제 출력 1

10

예제 입력 2

3 2
1 65
5 23
2 99
10
2

예제 출력 2

164

풀이(아주 간단)

우선 생각해야 할 것이, 이것은 절대로 냅색(Knapsack) 알고리즘같은 것이 아니다. 가방 문제 하면 가장 유명한 냅색 알고리즘이 튀어 나올 수 있지만, 제약 조건을 자세히 살피면 가방에는 단 한 개의 보석만을 넣을 수 있다.

말만 들으면 냅색+제약에 맞는 구현 쪽인 난이도 높은 문제같지만, 이 문제를 풀 때만큼은 중고등학교 때 처음 코딩을 배울 때로 돌아가야 한다.

1. 작은 가방에는 작은 돌이 들어간다.
2. 작은 돌들 중 가장 비싼 것을 가져가야 돈을 많이 벌 수 있다.
3. 말 그대로 정렬을 하자.
4. 오름차순이면 가방 안에 들어가는 돌들을 반복문으로 추리고 그 중 가장 큰 것을 찾자. 수익에 가격표 반영. 3.1. 넣은 돌 다음으로 비싼 돌은 다음 차례 가방에 들어가면서도 들어갈 수 있는 돌일지도 모른다. 오름차순이니 크기 문제는 좀 더 느슨하게 생각해도 되니 남은 돌들은 일단 남겨 놓자.
5. 다음 돌로 남은 돌 목록을 그대로 재활용해서 다시 3번 단계로 돌아간다.

우선순위 큐, 정렬, 그리고 보이는대로 쑤셔넣기, 이것이 전부이다. 그리디의 느낌은 분명 있지만, 가장 무식하게 그리디의 기초를 익힐 수 있는 방법이며, 우선순위 큐를 중점적으로 쓴다기보단 그냥 그때그때 정렬 돌리면 자원 낭비라서 “정렬된 상태”를 유지하기 위한 방법이다. 내가 이것을 우선순위 큐 문제로 분류하지 않은 것도 이런 맥락이라고 보면 된다.

주의할 점

• 우선순위 큐가 비었을 때 pop();을 돌리면 그냥 죽는다. C++의 상대적으로 오래된 기능인 STL 라이브러리는 이러한 방어를 사용자의 책임으로 위임한다. 설계 철학을 따라서 if(!pq.empty())같은 것을 잘 하는 것은 C++ 개발자의 소양 중 하나다.
• int 범위에서 계속 큰 수를 더할 수 있다는 게 문제 제약조건에서 암시되어 있다. 서서히 자료형을 늘려보자. 나의 경우에는 long int로 통과되었으며, 많은 코딩 테스트 플랫폼은 64-bit, Linux 4.x - 6.x, LP64, glibc 2.x 환경이다. 이러한 G환경에서 long int는 내부적으로 int64_t이기 때문에 통과된다.
  • (추가 팁) (보통 나의 경우 이런 음수 없는 문제들에선 int -> unsigned int -> long int-> unsigned long int -> long long -> unsigned long long 순으로 따라간다. 이 문제의 경우 Windows Enterprise Server + MSVC 및 LLP64 시스템 종류에서는 long long이 64-bit integer이다.)
• 보석더미를 처음부터 뒤지면 안 된다.
  • i를 그때그때 뒤진다 하면 i가 이미 전단계에서 나아가면서 우선순위 큐에 집어 넣은 것들이다.
    • 이미 들어간 것을 다시 넣는 중복 삽입은 메모리 낭비이다.
  • 실제 구현 시 바뀌지 않는다는 것을 강조하려면 for문 밖에 이터레이터를, 권장되지 않으나 굳이 for문에서 사용한다는 것을 강조하려면 for문 안에 static int를 두면 누적해서 이터레이터가 전진한다.
  • 이렇게 중간부터 보석을 뒤지는 방안을 활용하지 않은 풀이들은 사실상 통과하지 못한다.
• 우리가 알고 싶은 것은 보석의 가격 합이지, 무게 합이 아니다. 우선순위 큐에는 가격만 넣어도 된다.
  • 이렇게 하면 두 개의 정수 쌍을 다 넣는 것보다 절반 정도의 메모리를 차지한다.

풀이 코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

typedef pair<int, int> int_pair_t;

int main() {

  vector<int_pair_t> jewels; 
  vector<int>        bags;
  int N, K;
  cin >> N >> K;
  for(int i = 0; i < N; i++) {
    int weight, price;
    cin >> weight >> price;
    int_pair_t p = make_pair(weight, price); // tie the weight and price as a pair
    jewels.push_back(p);
  }
  for(int i = 0; i < K; i++) {
    int b;
    cin >> b;
    bags.push_back(b);
  }

  sort(bags.begin(), bags.end());     //sort, ascending
  sort(jewels.begin(), jewels.end()); // ..

  long int stolen_jewels_value = 0; // we only need sum of values

  priority_queue<int, vector<int>, less<int>> pq;
  int i = 0;
  for(auto b: bags) {
    for(;i < (int)jewels.size() && jewels[i].first <= b; i++) { // do not fully seek in every iteration
      pq.push(jewels[i].second);
    }

    if(!pq.empty()) {
      int jewel = pq.top();
      stolen_jewels_value += jewel;
      pq.pop();
    }
  }

  cout << stolen_jewels_value;
  return 0;
}

원리를 알고 나면 어렵지 않은 풀이지만, 원리를 알기 전에는 굉장히 어려워 보인다. 이러한 점을 유념해야 실전에서 더듬지 않을 수 있다.

오륜서의 저자이자 병법가였던 미야모토 무사시의 나온 어투로 글을 맺어 보고 싶다.

원리가 손에 자연히 익혀질 때까지 반복적으로 훈련하지 않으면 안 된다. 이후는 구전한다.

결론

이 문제의 본질은 어떻게 정렬하고, 어떻게 최대를 찾고, 어떻게 지우는지를 정렬과 우선순위 큐로 어떻게 해낼지를 짚는다. 이론적으로는 그리디 매칭 문제라고 부르지만, 나는 편의 상의 문제로 전문 용어 없이 정렬과 그리디를 어떻게 섞어내는 문제인지로 말하겠다.

이러한 풀이는 겉으로 보기에는 무서운 기세이지만 막상 그 속을 파고들면 어린아이도 풀 수 있는 유형이다. 코딩 테스트에서 나온다면 겁주기를 위한 문제일 수도 있고, 그것보다는 더 유형을 복잡하게 낼 수도 있다.

이 유형은 복잡한 그리디도 어려운 정렬 구현도 요구하지 않는다. “Mi, Vi, 보석점”같이 난이도를 착각하게 만드는 갑옷 사이의 빈틈을 잘 노려 벗겨내면 사실은 부드러운 속살이 드러나는, 대게와 같은 문제이다. 유형을 반복 숙달하고, 내가 보석을 단순한 돌로 언급했듯 불필요하게 장식적인 말들을 걷어내어 문제를 분석해야 한다. 이런 문제를 잘 발라 먹으면 변별력 문제를 틀릴 때의 실점을 만회할 기반을 다질 수 있다.

구전한다고 말했듯이, 이러한 유형의 문제를 블로그에서 집중적으로 다뤄볼 것이다. 이 과정을 잘 따라온다면 여러분도 알고리즘의 기초에 대해 공부할 수 있을 것이다.